package 中等.滑动窗口;

import java.util.Arrays;

/**
 * 给你一个下标从 0 开始的数组 nums 和一个整数 target 。
 * 下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
 * 请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，
 * 并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。
 *
 * @ https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/description/
 * @date 2024/08/12
 */
public class 无限数组的最短子数组_2875 {

    public static void main(String[] args) {

//        System.out.println(minSizeSubarray(new int[]{1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1}, 83));
        System.out.println(minSizeSubarray(new int[]{1, 6, 5, 5, 1, 1, 2, 5, 3, 1, 5, 3, 2, 4, 6, 6}, 56));

    }

    public static int minSizeSubarray(int[] nums, int target) {
        int ans = Integer.MAX_VALUE;

        int arrSum = Arrays.stream(nums).sum();
        int mod = target % arrSum;
        if (mod == 0) {
            return target / arrSum * nums.length;
        }

        int[] temp = new int[nums.length * 2];
        System.arraycopy(nums, 0, temp, 0, nums.length);
        System.arraycopy(nums, 0, temp, nums.length, nums.length);

        int left = 0, right = 0, sum = 0;
        while (right < temp.length) {
            sum += temp[right];
            right++;
            if (sum < mod) {
                continue;
            }

            while (left < right && sum >= mod) {
                if (sum == mod) {
                    ans = Math.min(ans, right - left);
                }

                sum -= temp[left];
                left++;
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : target / arrSum * nums.length + ans;
    }

}
